package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-12
 * Time:16:58
 */

import java.util.HashMap;

/**
 *
 牛客算法篇:BM51 数组中出现次数超过一半的数字
 描述
 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
 数据范围：n≤50000n≤50000，数组中元素的值 0≤val≤100000≤val≤10000
 要求：空间复杂度：O(1)O(1)，时间复杂度 O(n)O(n)
 输入描述：
 保证数组输入非空，且保证有解
 示例1
 输入：
 [1,2,3,2,2,2,5,4,2]
 返回值：
 2
 */
public class MoreThanHalfNum_Solution {
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        // write code here
//        HashMap<Integer,Integer> hash = new HashMap<>();
//        for(int i = 0;i < numbers.length;i++){
//            hash.put(numbers[i],hash.getOrDefault(numbers[i],0) + 1);
//        }
//        for (int i = 0; i < numbers.length; i++) {
//            if (hash.get(numbers[i]) > (numbers.length / 2)){
//                return numbers[i];
//            }
//        }
//        return -1;
        int candidate = numbers[0];
        int count = 1;

        for (int i = 1; i < numbers.length; i++) {
            if (count == 0) {
                candidate = numbers[i];
                count = 1;
            } else if (numbers[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
}
